package practise;

import java.util.Stack;

public class IsSameTree {
    public static boolean isSameTree(TreeNode p, TreeNode q) {

        Stack<TreeNode> pStack = new Stack<>();
        Stack<TreeNode> qStack = new Stack<>();
        TreeNode pTmp, qTmp;
        pStack.push(p);
        qStack.push(q);

        while(!pStack.isEmpty() && !qStack.isEmpty()) {
            pTmp = pStack.pop();
            qTmp = qStack.pop();
            if(pTmp == null && qTmp == null) {
                continue;
            }
            if(qTmp == null || pTmp == null) {
                return false;
            }
            if(pTmp.val != qTmp.val) {
                return false;
            }
            pStack.push(pTmp.left);
            pStack.push(pTmp.right);
            qStack.push(qTmp.left);
            qStack.push(qTmp.right);
        }
        return pStack.isEmpty() && qStack.isEmpty();
    }

    public static void main(String[] args) {
        TreeNode tree1 = new TreeNode(1);
        tree1.left = new TreeNode(2);
        tree1.right = new TreeNode(3);
        TreeNode tree2 = new TreeNode(1);
        tree2.left = new TreeNode(2);
        tree2.right = new TreeNode(3);
        isSameTree(tree1, tree2);
    }
}
